package com.dyz.leetcode._18_backtracking;

import com.dyz.leetcode.ListNode;
import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;


public class _112_hasPathSum {
    private List<List<Integer>> res;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> path = new ArrayList<>();
        res = new ArrayList<>();
        dfs(root, path);
        for(List<Integer> lists:res){
            int sum = 0;
            for(int num:lists){
                sum+=num;
            }
            if(sum==targetSum){return true;}
        }
        return false;

    }

    private void dfs(TreeNode node, List<Integer> path){
        if(node==null){return;}

        path.add(node.val);
        if(node.left==null && node.right==null){
            res.add(new ArrayList<>(path));
        }

        dfs(node.left, path);
        dfs(node.right, path);

        //回溯
        path.remove(path.size()-1);
    }

    private List<Integer> res1;
    public boolean hasPathSum1(TreeNode root, int targetSum) {
        int path = 0;
        res1 = new ArrayList<>();
        dfs1(root, path);
        for(int s:res1){
            if(s==targetSum){return true;}

        }
        return false;

    }

    private void dfs1(TreeNode node, int path){
        if(node==null){return;}

        path += node.val;
        if(node.left==null && node.right==null){
            res1.add(path);
        }

        dfs1(node.left, path);
        dfs1(node.right, path);

        //回溯
        path-=node.val;
    }

    public boolean hasPathSum2(TreeNode root, int targetSum) {
        List<Integer> res = new ArrayList<>();
        dfs2(root, targetSum, res);
        System.out.println(res);
        if(res.size()>0){return true;}
        return false;
    }
    private void dfs2(TreeNode node, int parentNodeTarget,  List<Integer> res) {
        if (node == null) {return;}
        int currNodeTarget = parentNodeTarget - node.val;
        if (node.left == null && node.right == null) {
            if(currNodeTarget==0){
                res.add(currNodeTarget);
            }
        }
        dfs2(node.left, currNodeTarget, res);
        dfs2(node.right, currNodeTarget, res);
    }

    public boolean hasPathSum3(TreeNode root, int target) {
        List<Integer> res = new ArrayList<>();
        boolean hasPathSum = dfs(root, target, res);
        System.out.println(res);
        return hasPathSum;
    }

    private boolean dfs(TreeNode node, int parentNodeTarget, List<Integer> res) {
        if (node == null) return false;

        res.add(node.val);

        int currNodeTarget = parentNodeTarget - node.val;
        if (node.left == null && node.right == null) {
            return currNodeTarget == 0;
        }
        boolean isLeftHasPathSum = dfs(node.left, currNodeTarget, res);
        // 提前退出
        if (isLeftHasPathSum) {return true;}
        boolean isRightHasPathSum = dfs(node.right, currNodeTarget, res);

        return isLeftHasPathSum || isRightHasPathSum;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(8);
        root.left = node1;
        root.right = node2;

        TreeNode node3 = new TreeNode(11);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(2);
        node1.left = node3;
        node3.left = node4;
        node3.right = node5;

        TreeNode node6 = new TreeNode(13);
        TreeNode node7 = new TreeNode(4);
        TreeNode node8 = new TreeNode(5);
        TreeNode node9 = new TreeNode(1);
        node2.left = node6;
        node2.right = node7;
        node7.left = node8;
        node7.right = node9;

        System.out.println(new _112_hasPathSum().hasPathSum(root, 22));
    }
}
